//SamXIAO
#include <cstdio>
#include <cstring>

#define szCNT_OF(x) (sizeof(x) / sizeof(x[0]))
#define MAX_LEN 20  // 1 * 1000 * 1000 + 86

long long dfs(int n, int k) {
   if (1 == k || 0 == n) return 1;
   if (n < k) return dfs(n, n);
   return dfs(n - k, k) + dfs(n, k - 1);
}

void work1() {
   int t;
   scanf("%d", &t);
   int n, k;
   while (t--) {
      scanf("%d%d", &n, &k);
      printf("%lld\n", dfs(n, k));
   }
}

int main() {
   work1();
   return 0;
}
